// 22.括号生成
package LeetcodeHot100;

import java.util.ArrayList;
import java.util.List;

public class Solution022 {
    public List<String> result = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        BackTrace(n, new StringBuilder(), 0, 0);

        return result;
    }

    private void BackTrace(int n, StringBuilder sb, int left, int right) {
        if (right > left || left > n || right > n)
            return;
        if (left == n && right == n) {
            result.add(sb.toString());
        }
        sb.append("(");
        BackTrace(n, sb, left + 1, right);
        sb.deleteCharAt(sb.length() - 1);
        sb.append(")");
        BackTrace(n, sb, left, right + 1);
        sb.deleteCharAt(sb.length() - 1);
    }

}
